package chapter25;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 所有节点对的最短路径-Jonhson
 */
public class Jonhson {

    public static int[][] johnson(Graph G) {
        EdgeNode se = new EdgeNode(0, 0);
        EdgeNode p = se;
        for (VertexNode vertexNode : G.adjList) {
            // TODO 深拷贝
            p.next = vertexNode.firstEdge;
            p = p.next;
        }
        VertexNode s = new VertexNode(se);
        G.adjList.add(s);
        G.numEdges += G.numVertexes;
        G.numVertexes++;

        if (!bellmanFord(G, s.firstEdge)) {
            System.out.println("the input graph contains a negative-weight cycle");
            return new int[][]{};
        } else {
            for (VertexNode vertexNode : G.adjList) {
                EdgeNode u = vertexNode.firstEdge;
                EdgeNode v = u.next;
                while (v != null) {
                    EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
                    if (v1.d <= u.d + v.weight) {
                        v1.h = u.d + v.weight;
                    }
                    v = v.next;
                }
            }
            int n = G.numVertexes;
            int[][] D = new int[n][n];
            for (VertexNode vertexNode : G.adjList) {
                EdgeNode u = vertexNode.firstEdge;
                EdgeNode v = u.next;
                while (v != null) {
                    EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
                    v1.weight += u.h - v.h;
                    v = v.next;
                }
                for (VertexNode vertexNode1 : G.adjList) {
                    Dijkstra(G, vertexNode1.firstEdge);
                    EdgeNode u1 = vertexNode.firstEdge;
                    EdgeNode v1 = u.next;
                    while (v1 != null) {
                        EdgeNode v2 = G.adjList.get(v1.adj).firstEdge;
                        D[u1.adj][v1.adj] = u.d + u1.h + v2.h;

                        v1 = v1.next;
                    }
                }
            }
            return D;
        }
    }

    public static void Dijkstra(Graph G, EdgeNode s) {
        initializeSingleSource(G, s);
        List<EdgeNode> edges = new ArrayList<>();
        for (VertexNode v : G.adjList) {
            EdgeNode pre = v.firstEdge;
            edges.add(pre);
        }
        sort(edges);
        for (EdgeNode u : edges) {
            EdgeNode v = u.next;
            while (v != null) {
                EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
                relax(u, v1, v.weight);

                v = v.next;
            }
        }
    }

    private static void sort(List<EdgeNode> edges) {
        sort(edges, 0, edges.size() - 1);
    }

    private static void sort(List<EdgeNode> edges, int p, int r) {
        if (p < r) {
            int q = partition(edges, p, r);
            sort(edges, p, q - 1);
            sort(edges, q + 1, r);
        }
    }

    private static int partition(List<EdgeNode> edges, int p, int r) {
        EdgeNode edge = edges.get(r);
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (edges.get(j).key < edge.key) {
                i++;
                EdgeNode temp = edges.get(j);
                edges.set(j, edges.get(i));
                edges.set(i, temp);
            }
        }
        EdgeNode temp = edges.get(i + 1);
        edges.set(i + 1, edges.get(r));
        edges.set(r, temp);
        return i + 1;
    }


    public static void initializeSingleSource(Graph G, EdgeNode s) {
        for (VertexNode v : G.adjList) {
            v.firstEdge.d = Integer.MAX_VALUE;
            v.firstEdge.pai = null;
        }
        s.firstEdge.d = 0;
    }


    public static void relax(EdgeNode u, EdgeNode v, int w) {
        if (v.d > u.d + w) {
            v.d = u.d + w;
            v.pai = u;
        }
    }

    public static boolean bellmanFord(Graph G, EdgeNode s) {
        initializeSingleSource(G, s);
        for (int i = 0; i < G.numVertexes; i++) {
            for (VertexNode vertexNode : G.adjList) {
                EdgeNode u = vertexNode.firstEdge;
                EdgeNode v = u.next;
                while (v != null) {
                    EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
                    relax(u, v1, v.weight);
                    v = v.next;
                }
            }
        }
        for (VertexNode vertexNode : G.adjList) {
            EdgeNode u = vertexNode.firstEdge;
            EdgeNode v = u.next;
            while (v != null) {
                EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
                if (v1.d > u.d + v.weight) {
                    return false;
                }
                v = v.next;
            }
        }
        return true;
    }

    public static void insert(EdgeNode x, EdgeNode y, int w) {
        EdgeNode pre = x;
        while (pre.next != null) {
            pre = pre.next;
        }
        y.firstEdge = x;
        y.weight = w;
        pre.next = y;
    }

    public static class EdgeNode {
        public int key;
        public int weight;
        public EdgeNode firstEdge = this;
        public EdgeNode next;
        public int adj;
        public int d = Integer.MAX_VALUE;
        public EdgeNode pai;
        public int h;
        public int w1;

        public EdgeNode(int key, int adj) {
            this.key = key;
            this.adj = adj;
        }

        public int getWeight() {
            return weight;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EdgeNode edgeNode = (EdgeNode) o;
            return Objects.equals(key, edgeNode.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }

        @Override
        public String toString() {
            return "{" +
                    "u='" + firstEdge.key + '\'' +
                    ", v='" + key + '\'' +
                    ", d=" + d +
                    '}';
        }
    }

    public static class VertexNode {
        public String key;
        public EdgeNode firstEdge;

        public VertexNode(EdgeNode firstEdge) {
            this.firstEdge = firstEdge;
        }

        @Override
        public String toString() {
            return "VertexNode{" +
                    "key='" + key + '\'' +
                    ", firstEdge=" + firstEdge +
                    '}';
        }
    }

    public static class Graph {
        public List<VertexNode> adjList = new ArrayList<>();
        public int numVertexes;
        public int numEdges;

        @Override
        public String toString() {
            return "Graph{" +
                    "adjList=" + adjList +
                    ", numVertexes=" + numVertexes +
                    ", numEdges=" + numEdges +
                    '}';
        }
    }
}
